EditDistance.java

packagesection19_DynamicProgramming;

publicclassEditDistance {

publicstaticvoidmain(String[] args) {

Strings1 = "agbg";
Strings2 = "acgb";

System.out.println(editDistance(s1, s2)); // 2
System.out.println(editDistanceIterative(s1, s2)); // 2
 }

// minimum changes required to make s2 equal to s1
// O(2^nm) Time, where n is length of s1, m is length of s2
publicstaticinteditDistance(Strings1, Strings2) {

if (s1.length() == 0)
returns2.length();

if (s2.length() == 0)
returns1.length();

Stringros1 = s1.substring(1);
Stringros2 = s2.substring(1);
intresult = 0;

if (s1.charAt(0) == s2.charAt(0)) {
result = editDistance(ros1, ros2);
 } else {
intremoveFactor = 1 + editDistance(ros1, ros2);
intaddFactor = 1 + editDistance(ros1, s2);
intreplaceFactor = 1 + editDistance(s1, ros2);

result = Math.min(removeFactor, Math.min(addFactor, replaceFactor));
 }

returnresult;
 }

// DP approach
// O(nm) Time, where n is length of s1, m is length of s2
publicstaticinteditDistanceIterative(Strings1, Strings2) {
int[][] storage = newint[s1.length() + 1][s2.length() + 1];

// seed value
storage[s1.length()][s2.length()] = 0;

for (introw = s1.length(); row >= 0; row--) {
for (intcol = s2.length(); col >= 0; col--) {

if (row == s1.length()) {
storage[row][col] = s2.length() - col;
continue;
 }

if (col == s2.length()) {
storage[row][col] = s1.length() - row;
continue;
 }

if (s1.charAt(row) == s2.charAt(col)) {
storage[row][col] = storage[row + 1][col + 1];
 } else {
storage[row][col] = 1 + Math.min(storage[row + 1][col + 1],
Math.min(storage[row + 1][col], storage[row][col + 1]));
 }
 }
 }

returnstorage[0][0];
 }
}